package com.yanceysong.codetop.s61_s70;

import com.yanceysong.common.TreeNode;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.LinkedList;
import java.util.Queue;


public class S68_Easy_104_二叉树的最大深度 {
    /**
     * .S68_Easy_104_二叉树的最大深度
     * .<p>
     * .LeetCode题目链接: <a href="https://leetcode.cn/problems/maximum-depth-of-binary-tree/">104. 二叉树的最大深度</a>
     * .<p>
     * .题目描述：
     * .给定一个二叉树，找出其最大深度。二叉树的深度定义为：根节点到最远叶子节点的最长路径上的节点数量。
     * .说明：叶子节点是没有子节点的节点。
     * .<p>
     * .核心标签：树(Tree)、深度优先搜索(DFS)、广度优先搜索(BFS)、递归(Recursion)、层序遍历(Level Order)
     * .<p>
     * .示例一：
     * .输入：root = [3,9,20,null,null,15,7]
     * .对应结构：
     * .           3
     * .         /   \
     * .        9    20
     * .            /  \
     * .           15   7
     * .输出：3
     * .<p>
     * .示例二：
     * .输入：root = []
     * .输出：0
     * .<p>
     * .示例三：
     * .输入：root = [1]
     * .输出：1
     * .<p>
     * .经典思路一（递归 DFS）：
     * .最大深度 = max(左子树最大深度, 右子树最大深度) + 1（当前根节点这一层）
     * .终止条件：空节点深度为 0。
     * .递归自顶向下逐层展开；也可自底向上理解：叶子返回 1，逐层累加。
     * .<p>
     * .经典思路二（迭代 BFS 层序遍历）：
     * .利用队列按层遍历，每遍历完一层，深度 +1。直到队列为空。
     * .<p>
     * .思路三（迭代 DFS 使用栈）：
     * .使用栈保存 (节点, 到该节点的深度)，模拟递归栈。
     * .<p>
     * .为什么 DFS 和 BFS 都可行？
     * .- DFS 更自然表达“当前节点的答案依赖子问题”
     * .- BFS 更直观统计“层数”
     * .<p>
     * .常见陷阱：
     * .1. 把“高度”和“深度”搞混；本题求根节点出发的最大深度（节点层数）。
     * .2. 误返回左右深度之和；正确是取最大值再 +1。
     * .3. 遗忘空树返回 0。
     * .<p>
     * .ASCII 图解（示例一）：
     * .层级/深度索引（从1开始）：
     * .depth=1              [3]
     * .depth=2         [9]     [20]
     * .depth=3               [15]  [7]
     * .最大深度 = 3。
     * .<p>
     * .复杂度分析：
     * .- 时间复杂度：O(n)，n为节点总数。每个节点访问一次。
     * .- 空间复杂度：
     * .  * .递归：最坏（链式退化）O(n)，平均平衡树 O(log n)（递归栈）。
     * .  * .BFS：最坏 O(n)（最后一层可能占用 ~n/2 个节点）。
     * .<p>
     * .关键洞察：
     * .“最大深度”是典型的“整棵树属性取决于子树属性”问题 -> 适合递归。
     * .空节点的深度定义为 0 能统一公式：max(left, right) + 1。
     * .<p>
     * .扩展：最小深度、直径、平衡判断都与“深度”相关，其递归模板与本题高度相似。
     */
    public int maxDepth(TreeNode root) {
        // 递归写法（DFS）：如果节点为空，深度为0
        if (root == null) {
            return 0;
        }
        // 递归求左/右子树的最大深度
        int leftSubtreeDepth = maxDepth(root.left); // 左子树最大深度
        int rightSubtreeDepth = maxDepth(root.right); // 右子树最大深度
        // 当前节点的最大深度 = 较大的子树深度 + 1（包含当前节点这一层）
        return Math.max(leftSubtreeDepth, rightSubtreeDepth) + 1;
    }

    /**
     * .迭代 BFS（层序遍历）方式获取最大深度。
     * .使用队列，每次弹出一层的所有节点，统计层数。
     */
    public int maxDepthBFS(TreeNode root) {
        if (root == null) {
            return 0;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int depth = 0;
        while (!queue.isEmpty()) {
            int levelSize = queue.size(); // 当前层节点数量
            // 遍历当前层
            for (int i = 0; i < levelSize; i++) {
                TreeNode current = queue.poll();
                if (current.left != null) {
                    queue.offer(current.left);
                }
                if (current.right != null) {
                    queue.offer(current.right);
                }
            }
            depth++; // 当前层处理完，深度 +1
        }
        return depth;
    }

    /**
     * .迭代 DFS（使用显式栈）方式获取最大深度，保存 (节点, 深度)。
     */
    public int maxDepthDFSIterative(TreeNode root) {
        if (root == null) {
            return 0;
        }
        Deque<TreeNode> nodeStack = new ArrayDeque<>();
        Deque<Integer> depthStack = new ArrayDeque<>();
        nodeStack.push(root);
        depthStack.push(1); // 根节点深度为 1
        int maxDepth = 0;
        while (!nodeStack.isEmpty()) {
            TreeNode current = nodeStack.pop();
            int currentDepth = depthStack.pop();
            maxDepth = Math.max(maxDepth, currentDepth);
            // 先压右后压左，使得左子树优先处理（非必须，只是一个访问顺序约定）
            if (current.right != null) {
                nodeStack.push(current.right);
                depthStack.push(currentDepth + 1);
            }
            if (current.left != null) {
                nodeStack.push(current.left);
                depthStack.push(currentDepth + 1);
            }
        }
        return maxDepth;
    }

    // ========================= 测试辅助方法 =========================

    /**
     * .构造示例一的树：root = [3,9,20,null,null,15,7]
     * .           3
     * .         /   \
     * .        9    20
     * .            /  \
     * .           15   7
     */
    private static TreeNode buildExampleTree1() {
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(9);
        root.right = new TreeNode(20);
        root.right.left = new TreeNode(15);
        root.right.right = new TreeNode(7);
        return root;
    }

    /**
     * .构造一棵完全二叉树：
     * .           1
     * .         /   \
     * .        2     3
     * .       / \   / \
     * .      4  5  6  7  深度=3
     */
    private static TreeNode buildCompleteTreeDepth3() {
        TreeNode n1 = new TreeNode(1);
        n1.left = new TreeNode(2);
        n1.right = new TreeNode(3);
        n1.left.left = new TreeNode(4);
        n1.left.right = new TreeNode(5);
        n1.right.left = new TreeNode(6);
        n1.right.right = new TreeNode(7);
        return n1;
    }

    /**
     * .构造一棵单链左倾树：1 -> 2 -> 3 -> 4 -> 5 (深度=5)
     */
    private static TreeNode buildLeftSkewed(int depth) {
        TreeNode head = null;
        for (int i = depth; i >= 1; i--) { // 从底向上构造，方便链接
            TreeNode node = new TreeNode(i);
            node.left = head;
            head = node;
        }
        return head;
    }

    /**
     * .构造一棵单链右倾树：1 -> 2 -> 3 -> 4 -> 5 (深度=5)
     */
    private static TreeNode buildRightSkewed(int depth) {
        TreeNode root = null;
        TreeNode prev = null;
        for (int i = 1; i <= depth; i++) {
            TreeNode node = new TreeNode(i);
            if (root == null) {
                root = node;
            } else {
                prev.right = node;
            }
            prev = node;
        }
        return root;
    }

    /**
     * .构造一棵不完全但较平衡的树：
     * .         1
     * .       /   \
     * .      2     3
     * .     /     / \
     * .    4     5   6
     * .         /
     * .        7        最大深度=4 (路径 1->3->5->7)
     */
    private static TreeNode buildUnbalancedButNotSkewed() {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.right.left = new TreeNode(5);
        root.right.right = new TreeNode(6);
        root.right.left.left = new TreeNode(7);
        return root;
    }

    // ========================= 简单断言辅助 =========================
    private static void assertEquals(int expected, int actual, String testName) {
        if (expected != actual) {
            throw new AssertionError(testName + " 失败: 期望=" + expected + ", 实际=" + actual);
        }
        System.out.println("✓ " + testName + " 通过 (深度=" + actual + ")");
    }

    /**
     * .主方法：运行多种测试场景，验证三种实现（递归、BFS、迭代DFS）的一致性。
     */
    public static void main(String[] args) {
        S68_Easy_104_二叉树的最大深度 solver = new S68_Easy_104_二叉树的最大深度();
        System.out.println("=== 二叉树最大深度 测试开始 ===\n");

        // 1. 空树
        TreeNode empty = null;
        int d1 = solver.maxDepth(empty);
        int d1b = solver.maxDepthBFS(empty);
        int d1d = solver.maxDepthDFSIterative(empty);
        assertEquals(0, d1, "空树-递归");
        assertEquals(0, d1b, "空树-BFS");
        assertEquals(0, d1d, "空树-迭代DFS");
        System.out.println();

        // 2. 单节点
        TreeNode single = new TreeNode(42);
        int d2 = solver.maxDepth(single);
        int d2b = solver.maxDepthBFS(single);
        int d2d = solver.maxDepthDFSIterative(single);
        assertEquals(1, d2, "单节点-递归");
        assertEquals(1, d2b, "单节点-BFS");
        assertEquals(1, d2d, "单节点-迭代DFS");
        System.out.println();

        // 3. 示例一
        TreeNode ex1 = buildExampleTree1();
        int d3 = solver.maxDepth(ex1);
        int d3b = solver.maxDepthBFS(ex1);
        int d3d = solver.maxDepthDFSIterative(ex1);
        assertEquals(3, d3, "示例一-递归");
        assertEquals(3, d3b, "示例一-BFS");
        assertEquals(3, d3d, "示例一-迭代DFS");
        System.out.println();

        // 4. 完全二叉树深度3
        TreeNode full3 = buildCompleteTreeDepth3();
        int d4 = solver.maxDepth(full3);
        int d4b = solver.maxDepthBFS(full3);
        int d4d = solver.maxDepthDFSIterative(full3);
        assertEquals(3, d4, "完全树-递归");
        assertEquals(3, d4b, "完全树-BFS");
        assertEquals(3, d4d, "完全树-迭代DFS");
        System.out.println();

        // 5. 左倾链
        TreeNode leftSkew = buildLeftSkewed(5);
        int d5 = solver.maxDepth(leftSkew);
        int d5b = solver.maxDepthBFS(leftSkew);
        int d5d = solver.maxDepthDFSIterative(leftSkew);
        assertEquals(5, d5, "左倾链-递归");
        assertEquals(5, d5b, "左倾链-BFS");
        assertEquals(5, d5d, "左倾链-迭代DFS");
        System.out.println();

        // 6. 右倾链
        TreeNode rightSkew = buildRightSkewed(6);
        int d6 = solver.maxDepth(rightSkew);
        int d6b = solver.maxDepthBFS(rightSkew);
        int d6d = solver.maxDepthDFSIterative(rightSkew);
        assertEquals(6, d6, "右倾链-递归");
        assertEquals(6, d6b, "右倾链-BFS");
        assertEquals(6, d6d, "右倾链-迭代DFS");
        System.out.println();

        // 7. 不完全但较平衡的树
        TreeNode unbalanced = buildUnbalancedButNotSkewed();
        int expectedDepthUnbalanced = 4;
        int d7 = solver.maxDepth(unbalanced);
        int d7b = solver.maxDepthBFS(unbalanced);
        int d7d = solver.maxDepthDFSIterative(unbalanced);
        assertEquals(expectedDepthUnbalanced, d7, "不完全平衡-递归");
        assertEquals(expectedDepthUnbalanced, d7b, "不完全平衡-BFS");
        assertEquals(expectedDepthUnbalanced, d7d, "不完全平衡-迭代DFS");
        System.out.println();

        // 8. 随机构造一棵较复杂树 (手动)
        //          10
        //        /    \
        //       5      12
        //      / \       \
        //     3   7       15
        //    /   / \     /
        //   1   6  8    13
        //                 \
        //                  14   最大深度: 5 (路径: 10->12->15->13->14 共5层)
        TreeNode r = new TreeNode(10);
        r.left = new TreeNode(5);
        r.right = new TreeNode(12);
        r.left.left = new TreeNode(3);
        r.left.right = new TreeNode(7);
        r.left.left.left = new TreeNode(1);
        r.left.right.left = new TreeNode(6);
        r.left.right.right = new TreeNode(8);
        r.right.right = new TreeNode(15);
        r.right.right.left = new TreeNode(13);
        r.right.right.left.right = new TreeNode(14);
        int d8 = solver.maxDepth(r);
        int d8b = solver.maxDepthBFS(r);
        int d8d = solver.maxDepthDFSIterative(r);
        assertEquals(5, d8, "复杂树-递归");
        assertEquals(5, d8b, "复杂树-BFS");
        assertEquals(5, d8d, "复杂树-迭代DFS");
        System.out.println();

        System.out.println("=== 所有测试完成 ===");
    }
}
